package binary

/**
 * @Author: zhangQi
 * @Date: 2020-09-19 14:04
 */

fun main(args: Array<String>) {
    print(sortedArray2.binarySearch(6))
}

fun List<Int>.binarySearch(item:Int):Int?{
    /**
     * 判定逻辑 list必须是顺序的,如果二分没结束(min<=max)
     * 则获取中间的数值
     * 将中间值做为左右判定的依据
     * 如果中间值刚好是要查找的数据,则直接返回 如1,2,3,4,5查找3
     * 如果中间值大于被查找的数,则最大值则=现在的中间值-1,因为中间值都大于item了,所以比中间值大的都忽略
     * 否则就是guess<item的情况,这情况下中间值小于查找,所以最小min变为中间值+1
     * 其中this[mid]是获取mid下标上的数据
     */
    var min = 0
    var max = lastIndex
    while(min<=max){
        val mid = (min+max)/2
        val guess = this[mid]
        if(guess == item) return mid
        if(guess > item) max = mid - 1
        else min = mid+1
    }
    return null
}

val sortedArray = (0..100 step 3).toList()
val sortedArray2 = (1..10).toList()

